package gold.digger;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC22 {

    public static Map<Integer, Set<String>> resultMap = new HashMap<>();

    public List<String> generateParenthesis_myWay(int n) {
        Set<String> re = new HashSet<>();
        if (1 == n) {
            re.add("()");
            resultMap.put(1, re);
            return new ArrayList<>(re);
        }

        if (null != resultMap.get(n)) {
            return new ArrayList<>(resultMap.get(n));
        }

        List<String> subRe = generateParenthesis_myWay(n - 1);
        for (String ele : subRe) {
            re.add("()" + ele);
            re.add(ele + "()");
            re.add("(" + ele + ")");
        }


        resultMap.put(1, re);
        return new ArrayList<>(re);
    }

    public List<String> generateParenthesis(int n) {
        Set<String> res = new HashSet<>();
        generateParenthesisDFS(n, n, "", res);
        return new ArrayList<>(res);
    }

    void generateParenthesisDFS(int left, int right, String out, Set<String> res) {
        if (left > right) return;
        if (left == 0 && right == 0) {
            res.add(out);
        } else {
            if (left > 0) generateParenthesisDFS(left - 1, right, out + '(', res);
            if (right > 0) generateParenthesisDFS(left, right - 1, out + ')', res);
        }
    }

    public static void main(String[] args) {
        LC22 an = new LC22();
        System.out.println(an.generateParenthesis(4));
    }
}
